1. Field of the Invention
The present invention relates to the field of memory management, in particular to efficient allocation of storage for performing numeric conversions with correctly rounded results.
2. Description of the Related Art
On a computer system, it is very common to convert numbers between a binary base and a decimal base. This is because most computer systems operate on binary numbers, whereas most commercial and scientific numerical operations are performed on numbers with a decimal base.
In many cases, conversions between numeric bases are approximations where numbers have a fractional portion. Such numbers are represented in binary as floating point numbers. A case where there is an exact representation is 0.5 (decimal) which is represented as 0.1 (binary). But for most cases, the fractional portion of a decimal number cannot be exactly converted. This phenomenon also occurs for large floating point numbers that cannot be exactly represented with limited significance of binary computer formats.
Numeric conversions are carried out in compilers, language libraries, interactive debuggers, digital signal processors, financial application software and for many other tools. Any system that must convert from one base numeric system to another base numeric system must perform such conversions. A complete discussion on the implications and effects of numeric representations and conversions is found in a publication entitled "Apple Numerics Manual, Second Edition", 1988 published by the Addison-Wesley Publishing Company, ISBN No. 0-201-17738-2.
As binary storage formats generally provide only close approximations to decimal values, it is important that conversions between the two types be as accurate as possible. Errors are introduced into a numeric representation when it is incorrectly rounded. A numeric representation may be incorrectly rounded when the representation does not contain enough information for making the rounding decision. As an example, when two numbers with fractional portion are multiplied, the fractional portion of the result is the sum of the widths of the fractional portions of the numbers being multiplied. In order to fit this back into the original numeric format, the result must be rounded. If there is not enough information to insure correct rounding, erroneous results may occur. Given a rounding direction, for every decimal value there is a best, correctly rounded, binary value for each binary format. Conversely, for any rounding direction, each binary value has a corresponding best decimal representation for a given decimal format. Ideally, conversion between binary and decimal conversions should obtain this best value to reduce accumulated errors and provide consistent results.
A typical way of converting a number between binary and decimal is to scale a binary integer by an appropriate power of ten. Previously, it has been necessary to compute to extremely high precision to guarantee correctly rounded conversions between binary and decimal. A known way to accurately scale a binary or decimal number by a binary power of ten is to require that both the number being scaled and the power of ten be exact. Conversions near the extremes of typical floating point ranges can require exact powers of ten near 10.sup.5000 whose exact representation requires 11,610 bits.
It is easy to perform the arithmetic but the storage required for computation is large and the computation times can be excessive. As a result, most commercial compilers and runtime systems use approximate conversions to reduce storage requirements and conserve computing resources.
It is known in the art to use extremely wide precision arithmetic to guarantee correctly rounded conversions. For example, in his Ph.D. Thesis entitled "Contribution to a Proposed Standard for Binary Floating-Point Arithmetic", Department of Mathematics, University of California, Berkeley, June 1984, Jerome T. Coonen, describes an algorithm using the extremely wide precision arithmetic concept. However, as noted above, use of extremely wide precision arithmetic requires large amounts of storage and a great deal of computing resource.
A second approach proposed by David M. Gay suggested that double precision arithmetic be used where suitable, and super high precision arithmetic be used when results are indecisive ("Correctly Rounded Binary-Decimal and Decimal-Binary Conversions", Technical Report, AT&T Bell Laboratories, November, 1990). However, this still does not negate the need for performing the super high precision when necessary.
Thus, in the known art, it is necessary to utilize large amounts of temporary storage to guarantee correct rounding results for all cases. It is an object of the present invention to provide an efficient and accurate method and apparatus for determining on efficient amount of storage needed for performing numerical base conversions an a computer system. Once this has been determined, efficient and correctly rounded base conversions can be guaranteed without 1) further difficult case checking or 2) potential large storage allocations. The minimal necessary storage allocation can be determined for specified source and destination formats.